/**
 * 236. 二叉树的最近公共祖先
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
 */
const { createTreeNode, findTreeNode } = require('../../libs/public');

/**
 * @param {TreeNode} node
 * @param {TreeNode} ref
 */
function isValueExist(node, ref) {
  if (!node) {
    return false;
  }
  if (node === ref) {
    return true;
  }
  if (isValueExist(node.left, ref)) {
    return true;
  }
  if (isValueExist(node.right, ref)) {
    return true;
  }
  return false;
}

let cache = null;

/**
 * @param {TreeNode} node
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
function find(node, p, q) {
  if (!node || cache) {
    return null;
  }
  if (node === p) {
    if (isValueExist(node.left, q) || isValueExist(node.right, q)) {
      cache = node;
      return null;
    }
    return node;
  }
  if (node === q) {
    if (isValueExist(node.left, p) || isValueExist(node.right, p)) {
      cache = node;
      return null;
    }
    return node;
  }
  let result = find(node.left, p, q);
  if (result === p) {
    if (isValueExist(node.right, q)) {
      cache = node;
      return null;
    }
    return result;
  }
  if (result === q) {
    if (isValueExist(node.right, p)) {
      cache = node;
      return null;
    }
    return result;
  }
  result = find(node.right, p, q);
  if (result === p) {
    if (isValueExist(node.left, q)) {
      cache = node;
      return null;
    }
    return result;
  }
  if (result === q) {
    if (isValueExist(node.left, p)) {
      cache = node;
      return null;
    }
    return result;
  }
  return null;
}

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
function lowestCommonAncestor(root, p, q) {
  find(root, p, q);
  const result = cache;
  cache = null;
  return result;
}

let tree;

tree = createTreeNode([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]);
console.log(lowestCommonAncestor(tree, findTreeNode(tree, 5), findTreeNode(tree, 1)).val === 3);

tree = createTreeNode([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]);
console.log(lowestCommonAncestor(tree, findTreeNode(tree, 5), findTreeNode(tree, 4)).val === 5);

tree = createTreeNode([1, 2]);
console.log(lowestCommonAncestor(tree, findTreeNode(tree, 1), findTreeNode(tree, 2)).val === 1);

tree = createTreeNode([37, -34, -48, null, -100, -101, 48, null, null, null, null, -54, null, -71, -22, null, null, null, 8]);
console.log(lowestCommonAncestor(tree, findTreeNode(tree, -71), findTreeNode(tree, 8)).val === -54);
